Communicating information in a communications network may be done in several ways. For example, a node in the network may transmit a message directly to an intended target node, or may transmit the message to one or more intermediate nodes with instructions to re-transmit the message until received by the target node. Another method of network communications is for a transmitting node to transmit a message so that all nodes in the network receive the message. Such a message would include information indicating that any receiving node re-transmit the message upon first receipt. However, unregulated retransmission of the message may result in nodes needlessly receiving the message multiple times, and some sort of algorithm or strategy is therefore needed to further reduce redundant message transmissions.
One strategy, known as Geoflood, uses location information to reduce the number of transmissions of a message where it is clear further transmissions of the message would only reach areas of the network already covered by previous transmissions of the message. Each message contains a location field that contains the geographic location of the node that has most recently transmitted the message. When a message is received by a node, the node computes how long it will hold the message before retransmitting it. FIG. 14 depicts a portion of a communications network 140 in which a receiving node R has a transmission radius 142. Transmission radius 142 defines a coverage area 144 of the receiving node. The coverage area is divided into four quadrants, namely the northeast quadrant NE, the northwest quadrant NW, the southeast quadrant SE, and the southwest quadrant SW. After receiving node R has established a holding time for the received message, the receiving node determines whether the same message has been received from neighboring nodes 146, 148, 150, 152 in each quadrant (NE, NW, SE, SW) of its coverage area before the holding time expires. According to the Geoflood algorithm, it is assumed that all or virtually all of coverage area 144 has received the message if the receiving node receives transmissions from neighboring nodes in each quadrant of the coverage area, and it is therefore not necessary for receiving node R to re-transmit the message.
The quadrant-based Geoflood algorithm just described was presumably chosen for its conceptual simplicity. However, accounting for the actual coverage area is a considerable bookkeeping challenge because each node must maintain four quadrant entries for each message during each holding time. Another disadvantage of the current Geoflood algorithm is shown in FIG. 15, in which the receiving node R receives transmissions from the four neighboring nodes 146, 148, 150, 152 in the respective quadrants NE, NW, SE, SW of coverage area 144 of the receiving node. According to the Geoflood algorithm, receiving node R does not re-transmit a received message, but there are portions 154, 156 of the coverage area that have not received the message from one of the neighboring nodes. Suppressing re-transmission of the message by receiving node R may result in nodes within portions 154, 156 not receiving the message. Thus, the Geoflood algorithm does not guarantee all of coverage area will receive a transmitted message.
Still another disadvantage of the Geoflood algorithm is that it requires redundant re-transmission of a message. At least four transmissions are required (one in each quadrant of a receiving node's coverage area) before re-transmission of the message is suppressed. As shown in FIG. 16 it is theoretically possible to fully account for all of a coverage area 144 of a receiving node R using the transmissions of three neighboring nodes 158, 160, 162 instead of four. However, because there is no transmission originating from a node in the southwest quadrant SW, the receiving node R will re-transmit a message when the coverage area 96 is already covered by the transmissions of the neighboring nodes 158, 160, 162. The quadrant-based Geoflood algorithm as currently instantiated is ill-suited to reduce these types of redundant transmissions.
It is therefore an object of the invention to provide a method of suppressing re-transmission of a message by a receiving node when neighboring nodes have already transmitted the message throughout the coverage area of the receiving node.
It is another object of the invention to provide a method of suppressing re-transmission of a message using an optimal number of transmissions from neighboring nodes.
It is still another object of the invention to provide a method of suppressing re-transmission of a message that ensures all parts of the coverage area of a receiving node can receive the message prior to suppression.
A feature of the invention is suppressing re-transmission of a message when the perimeter of the coverage area of a receiving node is completely overlapped, intersected, or covered by the coverage areas of other nodes that have transmitted the message to the receiving node.
An advantage of the invention is that before a node suppresses re-transmission of a message, all portions of the node's coverage area can receive the message from other nodes.
Another advantage is that the number of transmissions from neighboring nodes is optimized.